JOI 11予選 D 1年生(難易度5)
まずはこの問題を全探索により解くことを考える.
各隙間について$ +,-のどちらを使うか決めることによって, $ O(2^N)でこの問題を解くことができるがそれでは間に合わない.
動的計画法をマスターすることは, 本選進出するための最重要事項である. 自分がDPを学習した際, 最初はうまく漸化式を立てることができなかったが, たくさんの解説記事を読み, たくさんの問題を解くことによってだんだんとできるようになってきた. 感覚的なアルゴリズムなのでぜひこのように学習していただきたい.
便宜上, 入力の一番最後の値を$ sumとおく.
さて, この問題の場合は次のような漸化式を立てることができる(なお, 0-indexedで考える).
$ dp_{i, j}:= $ i番目まで見て, $ i番目までの和が$ jのときの正しい等式の個数.
するとこの漸化式は次のように更新できる.
$ dp_{0, a_0} = 1(初期化)
$ iは$ 0から$ N - 2まで,$ jは$ 0から$ 20まで動かす .
$ dp_{i+1, j+a_{i+1}} = dp_{i+1, j+a_{i+1}} + dp_{i,j}(ただし, $ 0 \leq j+a_{i+1} \leq 20を満たすとき)
$ dp_{i+1, j-a_{i+1}} = dp_{i+1, j-a_{i+1}} + dp_{i,j}(ただし, $ 0 \leq j-a_{i+1} \leq 20を満たすとき)
このようにすることによって, $ dp_{N-1, sum}が答えとなる. 計算量は$ O(N)となり, 十分間に合う.